package scoutobahn.dijkstra;

import java.util.Collection;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.TreeSet;
import java.util.Comparator;

import scoutobahn.highway.HighwayGraph;
import scoutobahn.highway.HighwayNode;
import scoutobahn.highway.Town;
import scoutobahn.highway.Highway;
import scoutobahn.util.Tuple;

import java.util.List;

/**
 * Contains methods to calculate
 * the shortest way from a given start-town to a given end-town
 * on a given HighwayGraph.
 * @author Richard, Antonio
 */

public class Dijkstra {

    private TreeSet<Edge> openEdges;
    private LinkedList<Edge> finishedEdges;
    private HashSet<HighwayNode> nodesNearEndTown;
    private HashSet<HighwayNode> nodesNearStartTown;
    private HighwayGraph highwayGraph;
/**
 * Constructor of the 'Dijkstra'-class.
 * @param pGraph (the given HighwayGraph)
 */
    public Dijkstra(final HighwayGraph pGraph) {
        highwayGraph = pGraph;
    }

    /**
     * Initializes the Dijkstra-algorithm by creating the openEdges-TreeSet
     * and the finishedEdges LinkedList,
     * it also determines the nodes near the start and the end
     * and puts them into the corresponding HashSets.
     * @param start (Name of the start-town)
     * @param end (Name of the end-town)
     */
    private void initiateDijkstra(final String start, final String end) {
        openEdges = new TreeSet<Edge>(new Comparator<Edge>() {
            public int compare(final Edge x, final Edge y) {
                if (x.getToNode().getDistanceToStart()
                        > y.getToNode().getDistanceToStart()) {
                    return 1;
                }
                if (x.getToNode().getDistanceToStart()
                        < y.getToNode().getDistanceToStart()) {
                    return -1;
                }
                return 0;
            }
        });
        finishedEdges = new LinkedList<Edge>();
        nodesNearStartTown = getNodesNearTown(start);
        for (HighwayNode node : nodesNearStartTown) {
            node.setMarked(true);
        }
        nodesNearEndTown = getNodesNearTown(end);

    }

    /**
     * Returns the nodes from the given town.
     * @param town (either start- or end-town)
     * @return HashSet of HighwayNodes
     */
    private HashSet<HighwayNode> getNodesNearTown(final String town) {
        Collection<Town> towns = highwayGraph.getTowns();
        HashSet<HighwayNode> nodesNearTown = new HashSet<HighwayNode>();
        for (Town t : towns) {
            if (t.getOsmItem().getTag("name") == town) {
                for (HighwayNode node : t.getNodeParents()) {
                    nodesNearTown.add(node);
                }
                return nodesNearTown;
            }
        }
        return null;
    }

    /**
     * Proves, if the next Nodes of the given Node are already marked.
     * If one is not marked,
     * an Edge will be made out of this and the given Node.
     * This new Edge is then added to the openEdges TreeSet.
     * @param node (node from which the edges will be generated)
     */
    private void addEdgesToList(final DijkstraNode node) {
        for (Highway highway : node.getHighwayNode().getHighwayParents()) {
            Tuple<HighwayNode, HighwayNode> nextIntersections
            = highway.getNextIntersections(node.getHighwayNode());
            if (nextIntersections.getItemOne() != null
                    && !nextIntersections.getItemOne().isMarked()) {
            double length = highway.getDistance(node.getHighwayNode(),
                    nextIntersections.getItemOne());
            Edge edge = new Edge(highway, node,
                    new DijkstraNode(nextIntersections.getItemOne()
                            , node.getDistanceToStart() + length,
                            highway) , length);
            openEdges.add(edge);
            }
            if (nextIntersections.getItemTwo() != null
                    && !nextIntersections.getItemTwo().isMarked()) {
            double length = highway.getDistance(node.getHighwayNode()
                    , nextIntersections.getItemTwo());
            Edge edge = new Edge(highway, node
                    , new DijkstraNode(nextIntersections.getItemTwo()
                            , node.getDistanceToStart() + length,
                            highway) , length);
            openEdges.add(edge);
            }
        }
    }


    /**
     * Recursive method, which returns a list of nodes,
     * which are on the shortest way from the start to the end.
     * @param nextNode (the next node on the shortest route)
     * @return LinkedList of DijkstraNodes
     */
    private List<DijkstraNode> generateRouteList(final DijkstraNode nextNode) {
        List<DijkstraNode> routeList;
        if (nodesNearStartTown.contains(nextNode.getHighwayNode())) {
        routeList = new LinkedList<DijkstraNode>();
        routeList.add(nextNode);
        return routeList;
        }

        for (Edge edge : finishedEdges) {
            if (edge.getToNode().equals(nextNode)) {
                routeList = generateRouteList(edge.getFromNode());
                routeList.add(nextNode);
                return routeList;
            }
        }
        return new LinkedList<DijkstraNode>();
    }

    /**
     * The "heart" of the 'Dijkstra'-class,
     * it calculates the shortest ways by
     * determining the shortest edge inside the openEdge TreeSet,
     * and checks if it leads to the end-town.
     * If so, it returns the list of nodes of the shortest way
     * given by the method 'generateRouteList'.
     * @param startTown (town where the route starts)
     * @param endTown (town where the route ends)
     * @return LinkedList of DijkstraNode
     */
    public List<DijkstraNode> getRoute(final String startTown
                                        , final String endTown) {

        initiateDijkstra(startTown, endTown);
        for (HighwayNode node : nodesNearStartTown) {
        addEdgesToList(new DijkstraNode(node, 0, null));
        }
        while (!openEdges.isEmpty()) {
            Edge minDistanceEdge = openEdges.first();

            minDistanceEdge.getToNode().getHighwayNode().setMarked(true);
            finishedEdges.add(minDistanceEdge);
            if (nodesNearEndTown.contains(
                    minDistanceEdge.getToNode().getHighwayNode())) {
                return generateRouteList(minDistanceEdge.getToNode());
            }
            openEdges.remove(minDistanceEdge);
            LinkedList<Edge> edgesToRemove = new LinkedList<Edge>();
            for (Edge edge : openEdges) {
                if (edge.getToNode() == minDistanceEdge.getToNode()) {
                    edgesToRemove.add(edge);
                }
            }

            addEdgesToList(minDistanceEdge.getToNode());
            openEdges.removeAll(edgesToRemove);

        }
        return new LinkedList<DijkstraNode>();
    }
}
